import java.util.ArrayList;
import java.util.List;

/**
 * 
 */

/**
 * @author zhongfang
 *
 */
public class FindDisppearedNums {
    public static List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> result=new ArrayList<>();
        boolean isEnding=false;//用isEnding检查是否所有位置不是-1就是i+1
        boolean isExist=false;//是否从上一个位置取出了数字
        int i=0;//代表找到的位置
        while(!isEnding){
            isEnding=true;
            i=0;
            while(i<nums.length){
                if((nums[i]!=i+1)&&(nums[i]!=-1)){//没有重复，可以放进去
                    isEnding=false;
                    int tmp=nums[i];
                    if(isExist){//如果有可以放进去的值，就先取出来再放进去
                        nums[i]=i+1;
                    }else{//否则，只能取出来，并把-1放进去
                        nums[i]=-1;
                    }
                    i=tmp-1;
                    isExist=true;
                }else{//如果相等，那么就重复了不需要放进去，直接往前面去;碰到了-1，如果需要放进去，就先放进去，再往后面去
                	if(isExist&&nums[i]==-1){
                		nums[i]=i+1;
                	}
                    i++;
                    isExist=false;
                }
            }
        }
        for(i=0;i<nums.length;i++){
            if(nums[i]==-1){
                result.add(i+1);
            }
        }
        return result;
    }
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(findDisappearedNumbers(new int[]{10,2,5,10,9,1,1,4,3,7}));;
	}

}
